﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【进阶】49.二叉树


//【头文件包含】

#include"BinaryTree.h"
#include"Queue.h"


//【结构体声明】
/*定义一种链式树结构*/typedef struct TreeNode
{
	int val;
	struct TreeNode* leftChild;
	struct TreeNode* rightBrother;
};

//【函数声明】
void Test1();

//【主函数】
int main()
{

	Test1();

	
	return 0;
}

//【函数】
/*测试用例*/void Test1()
{
	printf("****测试用例开始****\n");
	//构建一颗测试用的伪二叉树
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_6 = (BTNode*)malloc(sizeof(BTNode));
	root->data = 'A'; root->left = node_1; root->right = node_2;
	node_1->data = 'B';node_1->left = node_3;node_1->right = node_4;
	node_2->data = 'C';node_2->left = node_5;node_2->right = node_6;
	node_3->data = 'D';node_3->left = NULL;node_3->right = NULL;
	node_4->data = 'E';node_4->left = NULL;node_4->right = NULL;
	node_5->data = 'F';node_5->left = NULL; node_5->right = NULL;
	node_6->data = 'G';node_6->left = NULL;node_6->right = NULL;

	printf("前序遍历\n");
	PrevOrder(root);
	printf("\n");
	printf("中序遍历\n");
	MidOrder(root);
	printf("\n");
	printf("后序遍历\n");
	NextOrder(root);
	printf("\n");
	printf("计算二叉树大小\n");
	int size = TreeSize(root);
	printf("size = % d\n", size);
	size=TreeLeafSize(root);
	printf("leafnums = % d\n", size);
	size = TreeDepth(root);
	printf("depth = % d\n", size);
	int k = 3;
	size = TreeLevelKSize(root, k);
	printf(" 第%d层有=%d个节点\n", k,size);

	char str[100] = "abc##de#g##f###";
	int i = 0;
	BTNode* root2=gettreebyprevprint(str, &i);
	PrevOrder(root2);
	printf("\n");
	MidOrder(root2);
	printf("\n");
	BTDataType x = 'c';
	BTNode* root3 = TreeFind(root2, x);
	if (root3 != NULL)printf("%c\n", root3->data);
	else
	{
		printf("NULL\n");
	}
	TreeLevelOrder(root);
	TreeLevelOrder(root2);
	printf("root: %d ,root2 %d\n", TreeComplete(root), TreeComplete(root2));
	DestoryTree(root);
	DestoryTree(root2);
	root = NULL;
	root2 = NULL;
	root3 = NULL;
	printf("****测试用例结束****\n");
}


//【笔记】
//48.二叉树
	//已知一个
	//求二叉树第k层的节点数，可以分解为这个二叉树左右子树的第k-1层的节点数之和，如果根为空返回0，向下递归直至k=1：返回1；
	//层序遍历利用队列思想，先进先出
		//根先进队列，迭代：队列不为空出头数据，头数据子节点入队，直到队列为空 
	


